package sort;
/**
 * 快速排序法实现
 * @author Heng
 *思路：采用分治递归的思路，将数组无线分支
 * 选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）
 * 越是杂乱物种的数，越快
 */
public class quitSort {
	public static void main(String[] args){
		int[] array = {7,6,8,0,15,23,2,3,5};
//		sort(array,0,array.length-1);

		for(int i = 0; i < array.length; i++){
			System.out.println(array[i]);
		}
	}
	/**
	 * 快速排序--固定切分的
	 * 可优化的部分--基准值可以采用起始、中间、和末尾的中间值
	 * @param array 整个需要排序的数组
	 * @param low 子数组的开头 
	 * @param hight 子数组的结尾 
	 */
	public static void sort(int[] array, int low, int hight){
		int start = low;
		int end = hight;
		// 定一个基准值 ---一般是数组的头一个值
		//		int keyValue = array[low];
		// 或者基准值为开头、结尾以及数组中间值的一个中间的值
		int middleIndex = (low + hight) / 2;
		int keyValue = getMiddleNum(array[low] , array[hight] , array[middleIndex]) ;
		
		while(end > start){
			// 从后到前，找到比基准值小的值
			while(end > start && array[end] >= keyValue){
				end--;
			}
			if(array[end] <= keyValue){
				int temp = array[end];
				array[end] = array[start];
				array[start] = temp;
			}
			// 从前面开始找比基准值大的数
			while(end > start && array[start] <= keyValue){
				start++;
			}
			if(array[start] >= keyValue){
				int temp = array[end];
				array[end] = array[start];
				array[start] = temp;
			}
		}
		// 分别开始对区分出来的左右两边进行排序
		if(start > low){
			sort(array,low,start-1);
		}
		if(end < hight){
			sort(array,end+1,hight);
		}
	}
	/**
	 * 三个数取中间值
	 * @param a
	 * @param b
	 * @param c
	 * @return 返回三个数中间的那个数
	 */
	public static int getMiddleNum(int a,int b, int c){
		if(a > b){
			if(a > c){
				return b > c?b:c;
			}else {
				return a;
			}
		}else{
			if(b > c){
				return a > c ?a:c;
			}else{
				return b;
			}
		}
	}
}
